package com.xiaoyu.dp;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 打家劫舍2
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
 * 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
 *
 * 示例1：
 *
 * 输入：nums = [2,3,2]
 * 输出：3
 * 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 *
 * @author: YuWenYi
 * @create: 2021-05-29 10:46
 **/
public class PlunderHouses2_213 {

    /*
    * 如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？
    * 如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；
    * 如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。
    *
    * 假设数组 nums 的长度为 n。
    * 如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0, n-2]
    * 如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1,n−1]
    * */
    public static int rob(int[] nums) {
        int len = nums.length;
        if (len == 1) return nums[0];
        if (len == 2) return Math.max(nums[0],nums[1]);
        int[] dp = new int[len];

        for (int i = 0; i <= len - 2; i++) {
            if (i >= 2){
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            }else {
                dp[0] = nums[0];
                dp[1] = Math.max(nums[0],nums[1]);
            }
        }
        int max1 = dp[len - 2];

        for (int i = 1; i <= len - 1; i++) {
            if (i >= 3){
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            }else {
                dp[1] = nums[1];
                dp[2] = Math.max(nums[1],nums[2]);
            }
        }
        return Math.max(max1, dp[len-1]);
    }


    //下面是更优的解,整体思路和上面的思路类似
    public int rob1(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    private int myRob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for(int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }


    public static void main(String[] args) {
        System.out.println(rob(new int[]{200,3,140,20,10}));
    }
}
